def calc_power_digraph(edges, nodes=[]):
    for edge in edges: assert len(edge) == 2
    edges = map(tuple, edges)
    nodes.extend(src for src, _ in edges); nodes.extend(dst for _, dst in edges)
    
    nodeInsOutsTable = dict(( n, ( [], [] ) ) for n in nodes) # node -> (list of node, list of node)
    for src, dst in edges: nodeInsOutsTable[src][1].append(dst); nodeInsOutsTable[dst][1].append(src)
    for _, ( ins, outs ) in nodeInsOutsTable.iteritems(): ins.sort(); outs.sort()
    
    insOutsNodeTable = dict() # (tuple of node, tuple of node) -> list of node
    for node, insOuts in sorted(nodeInsOutsTable.iteritems()):
        k = ( tuple(insOuts[0]), tuple(insOuts[1]) )
        insOutsNodeTable.setdefault(k, []).append(node)
    
    powerNodes = sorted(list(tuple(nodes) for nodes in insOutsNodeTable.itervalues()))
        # list of tuple of node # a power node is a set of (normal) nodes.
    
    hptbl = dict(( pn[0], pn ) for pn in powerNodes) # list -> tuple of node
    powerEdges = [( hptbl[src], hptbl[dst] ) for src, dst in edges if src in hptbl and dst in hptbl ] 
        # list of (power node, power node), that is, list of (tuple of node, tuple of node)
    
    return powerEdges, powerNodes

if __name__ == '__main__':
    edges = [ (1, 4), (1, 4), (2, 4), (2, 4), (3, 4) ]
    powerEdges, powerNodes = calc_power_digraph(edges)
    # note that node 3 is not merged to node 1 or 2,
    # because the algorithm is counting counting number of edges.
    # Both node 1 and 2 have two edges to node 4, while node 3
    # has one edge to node 4.
    
    pn12, pn3, pn4 = ( 1, 2 ), ( 3, ), ( 4, )
    assert powerNodes == [ pn12, pn3, pn4 ]
    assert powerEdges == [ ( pn12, pn4 ), ( pn12, pn4 ), ( pn3, pn4) ]
    
    pe, pn = calc_power_digraph(edges, [ 1, 2, 3, 4, 5 ]) # node 5 has no edges.
    assert pe == powerEdges
    assert pn == sorted(powerNodes + [ (5, ) ])
